We study the complexity of the destructive bribery problem---an externalagent tries to prevent a disliked candidate from winning by briberyactions---in voting over combinatorial domains, where the set of candidates isthe Cartesian product of several issues. This problem is related to the conceptof the margin of victory of an election which constitutes a measure ofrobustness of the election outcome and plays an important role in the contextof electronic voting. In our setting, voters have conditional preferences overassignments to these issues, modelled by CP-nets. We settle the complexity ofall combinations of this problem based on distinctions of four voting rules,five cost schemes, three bribery actions, weighted and unweighted voters, aswell as the negative and the non-negative scenario. We show that almost all ofthese cases are NP-complete or NP-hard for weighted votes while approximatelyhalf of the cases can be solved in polynomial time for unweighted votes.
展开▼
